前言

震惊！这种非主流的方法居然$A$了

解题思路

介绍一种不一样的思路，也就是不是DP的写法，

纯粹的最短路

数据范围比较小，然后又不同的天数

于是就可以搞分层图

改变路径的情况

只要在一层的 $n$ 号点与下一层 $1$ 号点之间连一条边权为 $K$ 的边

不改变路径的情况

这种情况比较复杂，但还是由于数据范围比较小，我们就可以愉快地暴力了

把每一种路径不改变的情况（称为阶段）求出来

先枚举 $i$，表示这一阶段的开始时间（即分层图上的第 $i$ 层），

再枚举 $j$，表示这一阶段的结束时间（即分层图上的第 $j$ 层），

期间，能用的点，应该在这阶段内的每一天都可以通过，

也就是只能走没标记过的点

对于每个阶段，也可以很愉快地跑最短路

跑完最短路的结果就是一次（跑一层）的费用，再乘上 层数，在第 $i$ 层的 $1$ 号点和第 $j$ 层的 $n$ 号点之间连边，也就是表示可以直接略过中间部分

最后再整体跑个图就好了

怎么可能没有坑

坑点就是，为了防止我们连在 $1$ 号点和 $n$ 号点的边更新 $n$ 号点所在层的其他节点的答案（毕竟你略过了中间部分就不能往回走了），所以在建图的时候，与 $n$ 号点相连的边由双向边改为单向边即可

Code

#include<bits/stdc++.h>
#define INF 0x7f7f7f7f
#define rgt register
#define M 10407
#define Mn 107
#define N 23
using namespace std;
struct Edge{
    int to,cost,nxt;
    Edge(int a,int b):to(a),cost(b) {}
    Edge(){    }
}b[M<<1];
struct node{
    int p,t,cost;
    node(int a,int b,int c):p(a),t(b),cost(c){}
    node(){}
    inline bool operator< (const node x) const{
        return cost>x.cost;
    }
};
int head[N],hed[Mn];//分别存点和时间
int n,m,t,T,K,D,d[N],s[N][Mn];//d数组是一层的最短路，s是分层图上最短路
bool vis[N],usd[N],gg[N][Mn];//usd记录一个阶段不能选的点有哪些
inline int read() {
    rgt int s=0;
    rgt char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) s=(s<<1)+(s<<3)+c-'0',c=getchar();
    return s;
}
inline void Add(int x,int y,int cost) {
    b[++t]=Edge(y,cost),b[t].nxt=head[x],head[x]=t;
}
inline void add(int x,int y,int cost) {
    b[++t]=Edge(y,cost),b[t].nxt=hed[x],hed[x]=t;
}
inline void Spfa() {//求一层的最短路
    int i,to,cur,cost;
    queue<int>p;p.push(1);
    memset(d,INF,sizeof(d)),d[1]=0,vis[1]=1;
    while(!p.empty()) {
        cur=p.front(),p.pop(),vis[cur]=0;
        for(i=head[cur];i;i=b[i].nxt) {
            to=b[i].to;
            if(usd[to]) continue;
            cost=d[cur]+b[i].cost;
            if(d[to]>cost) {
                d[to]=cost;
                if(!vis[to])
                    vis[to]=1,
                    p.push(to);
            }
        }
    }
}
inline void Dijstra() {//求整体的最短路
    int i,to,p,t,cost;
    bool vis[N][Mn];
    priority_queue<node>Q;Q.push(node(1,1,0));
    memset(s,INF,sizeof(s));s[1][1]=0;
    memset(vis,0,sizeof(vis));
    while(!Q.empty()) {
        p=Q.top().p,t=Q.top().t,Q.pop();
        if(vis[p][t]||t>T) continue;vis[p][t]=1;
        for(i=head[p];i;i=b[i].nxt) {
            to=b[i].to;if(gg[to][t]) continue;
            cost=b[i].cost+s[p][t];
            if(s[to][t]>cost) {
                s[to][t]=cost;
                Q.push(node(to,t,cost));
            }
        }
        if(p==1) {//特别的操作，其实就是为了减少连边数（有俩个关键字太烦了
            for(i=hed[t];i;i=b[i].nxt) {
                to=b[i].to,cost=b[i].cost+s[p][t];
                if(s[n][to]>cost) {
                    s[n][to]=cost;
                    Q.push(node(n,to,cost));
                }
            }
        }
        else if(p==n) {//这种情况直接特判，不用连边（因为太烦了
            if(s[1][t+1]>s[n][t]+K) {
                s[1][t+1]=s[n][t]+K;
                Q.push(node(1,t+1,s[1][t+1]));
            }
        }
    }
}
int main()
{
    int i,j,k,l,r,x,y,cost;
    T=read(),n=read(),K=read(),m=read();
    for(i=1;i<=m;i++)
    {
        x=read(),y=read(),cost=read();
        if(x==n) swap(x,y);//建图的时候n点连的是单向边
        if(y!=n) Add(y,x,cost);
        Add(x,y,cost);
    }
    D=read();
    while(D--) {
        x=read(),l=read(),r=read();
        for(i=l;i<=r;i++) gg[x][i]=1;//gg就是不能用
    }
    for(i=1;i<T;i++) {//枚举i
        for(k=1;k<=n;k++) usd[k]=gg[k][i];//
        for(j=i+1;j<=T;j++) {
            for(k=1;k<=n;k++) usd[k]|=gg[k][j];
            Spfa();if(d[n]!=INF) add(i,j,d[n]*(j-i+1));//如果不连通，就不能连，否则就会嘿嘿嘿
        }
    }Dijstra();
    printf("%d",s[n][T]);
    return 0;
}

devil.